package BackTrackingSeries;

public class ExistSolution_79 {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[0].length; y++) {
                if (backTracking(board, words, x, y, 0)) return true;
            }
        }
        return false;
    }

    public boolean backTracking(char[][] board, char[] word, int x, int y, int index) {
        // 回溯失败条件
        if (x >= board.length || y >= board[0].length || x < 0 || y < 0 || board[x][y] != word[index]) {
            return false;
        }

        //回溯成功结束条件
        if (index == word.length - 1) {
            return true;
        }

        board[x][y] = '.';
        boolean result = backTracking(board, word, x + 1, y, index + 1) || backTracking(board, word, x, y + 1, index + 1) || backTracking(board, word, x - 1, y, index + 1) || backTracking(board, word, x, y - 1, index + 1);
        board[x][y] = word[index];
        return result;
    }
}